package faction.shellSort;

import java.util.stream.IntStream;

/**
 * 希尔排序
 */
public class shellSort {
    public static void exec(int[] input) {
        int length = input.length;
        for(int gap = length / 2; gap > 0; gap=gap/2) {
            for (int i = gap; i  < length; i++) {
              int temp = input[i];
              int j = i;
              while (j >= gap && input[j - gap] > temp) {
                input[j] = input[j - gap];
                j -= gap;
              }
              input[j] = temp;
            }
        }
        IntStream intStream = IntStream.of(input);
        intStream.forEach(c->System.out.printf("%s\t", c));
        System.out.println();
    }

    public static void exec1(int[] arr) {
        int n = arr.length;
        
        // 初始增量设为数组长度的一半
        for (int gap = n / 2; gap > 0; gap /= 2) {
            IntStream intStream = IntStream.of(arr);
            intStream.forEach(c->System.out.printf("%s\t", c));
            System.out.println();
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j = i;
                while (j >= gap && arr[j - gap] > temp) {
                    System.out.println(arr[j - gap] + "\t" + j);
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
                System.out.println(temp + "\t" + j);
                System.out.println();
            }
        }       
        IntStream intStream = IntStream.of(arr);
        intStream.forEach(c->System.out.printf("%s\t", c));
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {1,12, 18,11, 13, 5, 6, 9, 27, 88, 32, 25};
        exec(arr);
    }
}
